let utils = data["utils"];
let STUtil = data["STUtil"];
let Node = data["Node"];
console.log("03Splaytree");

function SplayTree(comparator) {
  function DEFAULT_COMPARE(a, b) {
    return a > b ? 1 : a < b ? -1 : 0
  }
  void 0 === comparator && (comparator = DEFAULT_COMPARE), this._root = null, this._size = 0, this._comparator = comparator
}
utils.extend(SplayTree.prototype, {
  insert: function (key, data) {
    return this._size++ , this._root = STUtil.insert(key, data, this._root, this._comparator)
  },
  add: function (key, data) {
    var node = new Node(key, data);
    null === this._root && (node.left = node.right = null, this._size++ , this._root = node);
    var comparator = this._comparator,
      t = STUtil.splay(key, this._root, comparator),
      cmp = comparator(key, t.key);
    return 0 === cmp ? this._root = t : (cmp < 0 ? (node.left = t.left, node.right = t, t.left = null) : cmp > 0 && (node.right = t.right, node.left = t, t.right = null), this._size++ , this._root = node), this._root
  },
  remove: function (key) {
    this._root = this._remove(key, this._root, this._comparator)
  },
  _remove: function (i, t, comparator) {
    var x, cmp;
    return null === t ? null : 0 === comparator(i, (t = STUtil.splay(i, t, comparator)).key) ? (null === t.left ? x = t.right : (x = STUtil.splay(i, t.left, comparator)).right = t.right, this._size-- , x) : t
  },
  pop: function () {
    var node = this._root;
    if (node) {
      for (; node.left;) node = node.left;
      return this._root = STUtil.splay(node.key, this._root, this._comparator), this._root = this._remove(node.key, this._root, this._comparator), {
        key: node.key,
        data: node.data
      }
    }
    return null
  },
  findStatic: function (key) {
    for (var current = this._root, compare = this._comparator; current;) {
      var cmp = compare(key, current.key);
      if (0 === cmp) return current;
      current = cmp < 0 ? current.left : current.right
    }
    return null
  },
  find: function (key) {
    return this._root && (this._root = STUtil.splay(key, this._root, this._comparator), 0 !== this._comparator(key, this._root.key)) ? null : this._root
  },
  contains: function (key) {
    for (var current = this._root, compare = this._comparator; current;) {
      var cmp = compare(key, current.key);
      if (0 === cmp) return !0;
      current = cmp < 0 ? current.left : current.right
    }
    return !1
  },
  forEach: function (visitor, ctx) {
    for (var current = this._root, Q = [], done = !1; !done;) null !== current ? (Q.push(current), current = current.left) : 0 !== Q.length ? (current = Q.pop(), visitor.call(ctx, current), current = current.right) : done = !0;
    return this
  },
  range: function (low, high, fn, ctx) {
    for (var Q = [], compare = this._comparator, node = this._root, cmp; 0 !== Q.length || node;)
      if (node) Q.push(node), node = node.left;
      else {
        if ((cmp = compare((node = Q.pop()).key, high)) > 0) break;
        if (compare(node.key, low) >= 0 && fn.call(ctx, node)) return this;
        node = node.right
      } return this
  },
  keys: function () {
    var keys = [];
    return this.forEach((function (_a) {
      var key = _a.key;
      return keys.push(key)
    })), keys
  },
  values: function () {
    var values = [];
    return this.forEach((function (_a) {
      var data = _a.data;
      return values.push(data)
    })), values
  },
  min: function () {
    return this._root ? this.minNode(this._root).key : null
  },
  max: function () {
    return this._root ? this.maxNode(this._root).key : null
  },
  minNode: function (t) {
    if (void 0 === t && (t = this._root), t)
      for (; t.left;) t = t.left;
    return t
  },
  maxNode: function (t) {
    if (void 0 === t && (t = this._root), t)
      for (; t.right;) t = t.right;
    return t
  }
});

return {
  "utils": utils,
  "STUtil": STUtil,
  "Node": Node,
  "SplayTree": SplayTree
}